import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
 * Created by L.jp
 * Description:给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
 * User: 86189
 * Date: 2022-08-17
 * Time: 10:22
 */
public class Solution {
    //标记是否被访问过数组
    static boolean[] mark;
    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
        LinkedList<Integer> tmp=new LinkedList<>();
        mark=new boolean[num.length];
        //先排序有助于排除情况
        Arrays.sort(num);
        backTrack(num,tmp,ret);
        return ret;
    }
    private static void backTrack(int[] num, LinkedList<Integer> tmp, ArrayList<ArrayList<Integer>> ret) {
        //如果满足了三个数就添加到结果集
        if(tmp.size()== num.length){
            ret.add(new ArrayList<>(tmp));
        }
        //开始全排列
        for(int i=0;i< num.length;i++){
            //如果已经访问过，或者有重复数并且前一个数被回溯删除了标记
            if(mark[i] || i>0 && num[i]==num[i-1] && !mark[i-1]){
                continue;
            }
            //添加
            tmp.add(num[i]);
            //标记为已访问过
            mark[i]=true;
            //回溯找下一个
            backTrack(num,tmp,ret);
            //添加到结果集后删除最后一个
            tmp.removeLast();
            //删除标记，供下一次使用
            mark[i]=false;
        }
    }
    
    public static void main(String[] args) {
        int[] num={1,1,2};
        System.out.println(permuteUnique(num));
    }
}
